"""
桶排序：
    - 桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略
    - 平均情况的时间复杂度：O(nk)
    - 最坏情况的时间复杂度：O(n**2 *k)
    - 空间复杂度： O(n+k)
"""
from SortingAlgorithm.cal_time.cal_time import cal_time


@cal_time(name="桶的排序时间")
def bucket_sort(li, n=100, max_num=10000):
    buckets = [[] for _ in range(n)]  # 创建桶
    for var in li:
        i = min(var // (max_num // n), n-1)  # i表示var放到几号桶里
        buckets[i].append(var)

        # 保持桶内的顺序
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break

    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li


if __name__ == "__main__":
    import random
    li = [random.randint(0, 10000) for i in range(10000)]
    li = bucket_sort(li)

    # print(li)
